package com.atguigu.search;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 龍
 * 二分查找：1）首先确定数组的中间的下表mid=（left+right）/2
 * 2)1 findVal>arr[mid],说明数在mid的右边，因此需要向右递归
 * 2 findVal<arr[mid]，说明mid在左边，因此需要向左递归
 * 3 findVal==arr[mid] 说明找到了，就返回。
 * 3）结束条件：
 * 1 找到了就结束递归
 * 2 递归完整个数组，仍然没有找到findVal，也需要结束递归，即left>right时
 * 前提条件：必须是有序数组。
 * 存在的问题：当我们需要查找的数据在数组的开头或者结尾的时候，查找是十分的不划算的，需要进行多次查找
 * 插值算法：采用自适应来改变mid的位置。
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 8, 10, 89, 89, 89, 1000, 1234};
        List resultList = binarySearch(arr, 0, arr.length - 1, 89);
        System.out.println("resultList====" + resultList);
    }

    /**
     * @param array:要查找的数组
     * @param left：左边的索引。
     * @param right：右边的索引
     * @param findVal：要寻找的值
     * @return ：要查找的值的下表
     * 找出所有的符合条件的数值。
     */
    public static ArrayList binarySearch(int[] array, int left, int right, int findVal) {
        if (left > right) {
            return new ArrayList();
        }
        int mid = (left + right) / 2;
        int midVal = array[mid];
        if (findVal > midVal) {
            //向右递归
            return binarySearch(array, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            //向左递归
            return binarySearch(array, left, mid - 1, findVal);
        } else {
            ArrayList<Integer> ints = new ArrayList<Integer>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || array[temp] != findVal) {
                    break;
                }
                ints.add(temp);
            }
            ints.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > array.length-1 || array[temp] != findVal) {
                    break;
                }
                ints.add(temp);
                temp++;
            }
            return ints;
        }

    }
}
